/**
 *  @file    DelUniqueValue.c
 *  @brief   不带头结点单链表的“删除最小值”高效算法
 *           1️⃣ `delUniqueValue`：一次遍历删除 **唯一** 最小值节点
 *           2️⃣ `delMultiValue`：两次遍历删除 **所有** 最小值节点
 *           其余函数演示链表的创建、插入、打印、销毁等基础操作
 *
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025‑07‑01 16:05
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* ========================================================================== */
/*                               数据结构定义                                 */
/* ========================================================================== */

/**
 * @brief 单链表节点
 */
typedef struct node {
    int           data;   ///< 数据域
    struct node  *next;   ///< 指针域
} node, *link;

/* ========================================================================== */
/*                              基本工具函数                                  */
/* ========================================================================== */

/* ---------- 创建节点 ---------- */

/**
 * @brief 申请并初始化一个新节点
 * @param value  要存储的数据
 * @return       成功返回节点指针；失败返回 NULL
 */
link createNode(int value)
{
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;      // 内存不足

    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

/* ---------- 头插法 ---------- */

/**
 * @brief 头插法在不带头结点的链表头部插入新节点
 * @param head   指向“链表首节点指针”的指针
 * @param value  要插入的数据
 * @note  若链表为空，插入后 *head 指向新节点
 */
void insertHead(link *head, int value)
{
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = *head;
    *head = newNode;
}

/* ---------- 尾插法 ---------- */

/**
 * @brief 尾插法在链表尾部插入新节点
 * @param head   指向链表首节点指针的指针
 * @param value  要插入的数据
 * @note  复杂度 O(n)，可维护尾指针降到 O(1)
 */
void insertTail(link *head, int value)
{
    link newNode = createNode(value);
    if (newNode == NULL) return;

    /* 链表为空：新节点即为首节点 */
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    /* 链表非空：遍历到尾 */
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

/* ---------- 打印链表 ---------- */

/**
 * @brief 顺序打印链表数据
 * @param head  链表首节点指针
 */
void printList(link head)
{
    if (head == NULL) return;
    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/* ---------- 销毁链表 ---------- */

/**
 * @brief 释放链表所有节点的内存
 * @param head  指向链表首节点指针的指针
 */
void destroyLink(link *head)
{
    if (*head == NULL) return;

    link cur = *head;
    while (cur != NULL) {
        link temp = cur;
        cur = cur->next;
        free(temp);
    }
    *head = NULL;
}


/* ========================================================================== */
/*                       删除最小值——唯一版本 (O(n))                          */
/* ========================================================================== */

/**
 * @brief 删除链表中 **唯一** 的最小值节点（一次遍历）
 * @param head  指向链表首节点指针的指针
 *
 * @details 算法思想
 *   • `cur` 逐节点扫描，同时维护 `minPre` —— 当前已知最小值节点的前驱
 *   • 当发现 `cur->next->data` 更小，则更新 `minPre = cur`
 *   • 遍历结束后，`minPre->next` 即唯一最小值节点，脱链并释放即可
 *   ➡️ 时间 O(n)，空间 O(1)
 */
void delUniqueValue(link *head)
{
    if (*head == NULL) return;          /* 空链表 */

    link cur    = *head;                /* 扫描指针 */
    link minPre = NULL;                 /* 最小值节点前驱，NULL 表示最小值在首节点 */

    /* ---- 单趟扫描 ---- */
    while (cur->next != NULL) {
        if (cur->data > cur->next->data) {
            /* 发现更小值：cur 成为新最小值的前驱 */
            minPre = cur;
        }
        cur = cur->next;
    }

    /* ---- 删除最小值节点 ---- */
    if (minPre == NULL) {
        /* 最小值就是首节点 */
        link delNode = *head;
        *head = delNode->next;
        free(delNode);
    } else {
        /* 最小值在链表中部或尾部 */
        link delNode = minPre->next;
        minPre->next = delNode->next;
        free(delNode);
    }
}

/* ========================================================================== */
/*                      删除最小值——多重版本 (2×O(n))                         */
/* ========================================================================== */

/**
 * @brief 删除链表中 **所有** 最小值节点（可能出现多次）
 * @param head  指向链表首节点指针的指针
 *
 * @details 两阶段
 *   1️⃣ 首遍扫描确定最小值 `minValue`
 *   2️⃣ 再遍扫描删除所有 data == minValue 的节点
 *   ➡️ 时间 O(n) + O(n) = O(n)，空间 O(1)
 */
void delMultiValue(link *head)
{
    if (*head == NULL) return;          /* 空链表 */

    /* -------- 第 1 遍：找最小值 -------- */
    link cur = *head;
    int  minValue = cur->data;

    while (cur != NULL) {               /* 扫描完整链表 */
        if (cur->data < minValue) {
            minValue = cur->data;
        }
        cur = cur->next;
    }

    /* -------- 第 2 遍：删除所有最小值节点 -------- */

    /* 2‑A 处理链表开头可能连续的最小值 */
    while (*head != NULL && (*head)->data == minValue) {
        link delNode = *head;
        *head = delNode->next;
        free(delNode);
    }

    /* 2‑B 删除链表中部 / 末尾最小值节点 */
    link pre = *head;         /* 前驱指针，已知当前节点非最小值 */
    cur = (pre ? pre->next : NULL);

    while (cur != NULL) {
        if (cur->data == minValue) {
            pre->next = cur->next;     /* 脱链 */
            free(cur);
            cur = pre->next;           /* cur 前移，pre 不动 */
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
}


int main(void)
{
    link head = NULL;

    /* 构造链表：5 → 1 → 4 → 1 → 3 */
    insertHead(&head, 3);
    insertHead(&head, 1);
    insertHead(&head, 4);
    insertHead(&head, 1);
    insertHead(&head, 5);

    puts("Original list:");
    printList(head);

    delMultiValue(&head);      /* 删除所有最小值 1 */

    puts("After delMultiValue:");
    printList(head);           /* 预期：5 → 4 → 3 */

    destroyLink(&head);
    return 0;
}
